package ua.mykola.ds.list;

/**
 * Find the number of nodes in a singly link list, it can be both cyclic and acyclic
 */
public class NodeCounter
{

    public int count(Node head)
    {
        Node slow = head.next;
        if (slow == null)
        {
            return 1;
        }
        Node fast = head.next.next;
        if (fast == null)
        {
            return 2;
        }

        int halfLength = 1;
        while (fast != null && fast.next != null && (fast != slow))
        {
            fast = fast.next.next;
            slow = slow.next;
            halfLength++;
        }
        if (fast != slow)
        {
            if (fast == null)
            {
                return halfLength * 2 - 1;
            }
            else
            {
                return halfLength * 2;
            }

        }

        // find cycle length
        int cycleLength = 1;
        slow = slow.next;
        while (fast != slow)
        {
            slow = slow.next;
            cycleLength++;
        }

        // move fast ahead for cycle length
        slow = head;
        fast = head;
        for (int i = 0; i < cycleLength; i++)
        {
            fast = fast.next;
        }

        int length = 0;
        while (fast != slow)
        {
            fast = fast.next;
            slow = slow.next;
            length++;
        }
        length--;
        return length + cycleLength;
    }
}
